#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool isMatch(char l, char r) {
    return (l == '(' && r == ')') || (l == '[' && r == ']') || (l == '{' && r == '}');
}

bool isValid(string s) {
    stack<char> theStack;
    for (int i{}, len = s.size(); i < len; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            // 左括号 直接入栈
            theStack.push(c);
        } else if (theStack.empty() || !isMatch(theStack.top(), c)) {
            // 右括号 栈空说明已经不匹配了 栈不为空且不匹配
            return false;
        } else {
            // 匹配了 弹出
            theStack.pop();
        }
    }
    return theStack.empty();
}

int main() {
    cout << boolalpha;
    bool result = isValid("(([]{}))");
    cout << "result: " << result << "\n";

    return 0;
}